//给你一个链表数组，每个链表都已经按升序排列。 
//
// 请你将所有链表合并到一个升序链表中，返回合并后的链表。 
//
// 
//
// 示例 1： 
//
// 输入：lists = [[1,4,5],[1,3,4],[2,6]]
//输出：[1,1,2,3,4,4,5,6]
//解释：链表数组如下：
//[
//  1->4->5,
//  1->3->4,
//  2->6
//]
//将它们合并到一个有序链表中得到。
//1->1->2->3->4->4->5->6
// 
//
// 示例 2： 
//
// 输入：lists = []
//输出：[]
// 
//
// 示例 3： 
//
// 输入：lists = [[]]
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// k == lists.length 
// 0 <= k <= 10^4 
// 0 <= lists[i].length <= 500 
// -10^4 <= lists[i][j] <= 10^4 
// lists[i] 按 升序 排列 
// lists[i].length 的总和不超过 10^4 
// 
// Related Topics 链表 分治 堆（优先队列） 归并排序 👍 2039 👎 0

package leetcode.editor.cn;

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

class MergeKSortedLists {
    public static void main(String[] args) {
        Solution solution = new MergeKSortedLists().new Solution();
        ListNode listNode = new MergeKSortedLists().new ListNode(1);
        listNode.next = new MergeKSortedLists().new ListNode(4);
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    class Solution {
        /*public ListNode mergeKLists(ListNode[] lists) {
            if (lists == null && lists.length == 0) return null;
            if (lists.length == 1) return lists[0];
            ListNode head = lists[0];
            ListNode cur = head;
            for (int i = 1; i < lists.length; i++) {
                ListNode node = lists[i];
                ListNode newHead = new ListNode(0);
                ListNode newCur = newHead;
                while (cur != null && node != null) {
                    if (cur.val < node.val) {
                        newCur.next = cur;
                        cur = cur.next;
                        newCur = newCur.next;
                    }else {
                        newCur.next = node;
                        node = node.next;
                        newCur = newCur.next;
                    }
                }
                newCur.next = cur == null ? node : cur;
                cur = newHead.next;
            }

            return cur;
        }*/

        // 分治
        /*public ListNode mergeKLists(ListNode[] lists) {
            return merge(lists, 0, lists.length - 1);
        }

        public ListNode merge(ListNode[] lists, int l, int r) {
            if (l == r) return lists[l];
            if (l > r) return null;
            // 分儿治之
            int mid = (l + r) >> 1;
            // 左闭右开
            return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
        }

        public ListNode mergeTwoLists(ListNode A, ListNode B) {
            if (A == null || B == null) return A == null ? B : A;
            ListNode dummy = new ListNode(0);
            ListNode cur = dummy, a = A, b = B;
            while (a != null && b != null) {
                if (a.val < b.val) {
                    cur.next = a;
                    a = a.next;
                } else {
                    cur.next = b;
                    b = b.next;
                }
                cur = cur.next;
            }
            cur.next = a == null ? b : a;
            return dummy.next;
        }
    */

        // 优先级队列
        /*public ListNode mergeKLists(ListNode[] lists) {
            PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>((a, b) -> a.val - b.val);
            ListNode dummy = new ListNode(0);
            ListNode cur = dummy;
            // 将每个链表都节点按照从小到大放入队列
            for (ListNode node : lists) {
                if (node != null) {
                    queue.offer(node);
                }
            }

            while (!queue.isEmpty()) {
                ListNode node = queue.poll();
                cur.next = node;
                cur = cur.next;
                // 如果node节点不为空，继续入队
                if (node.next != null) {
                    queue.offer(node.next);
                }
            }

            return dummy.next;
        }*/


        public ListNode mergeKLists(ListNode[] lists) {
            PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>((a , b) -> a.val - b.val);
            ListNode dummy = new ListNode(-1);
            ListNode p = dummy;
            for (ListNode list : lists) {
                if (list != null) {
                    queue.offer(list);
                }
            }

            while (!queue.isEmpty()) {
                ListNode poll = queue.poll();
                p.next = poll;
                p = p.next;
                if (poll.next != null) {
                    queue.offer(poll.next);
                }
            }

            return dummy.next;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
